[NOIP2011]-观光公交

贪心, 费用流

题目链接

贪心

就是每次找一条 “如果使用加速器，能影响的人最多” 的边！

code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1010;
int n, m, K, d[N], pre[N], on[N], off[N], arri[N], use[N], ans;
// use[i] ��ʾ d[i]-- ���ж����������� 

int main() {
    //freopen("bus.in", "r", stdin);
    //freopen("bus.out", "w", stdout);
    
    scanf("%d%d%d", &n, &m, &K);
    for (int i = 1; i < n; i++) scanf("%d", &d[i]);
    for (int i = 1; i <= m; i++) {
        int t, a, b; scanf("%d%d%d", &t, &a, &b);
        ans -= t;
        on[a] = max(on[a], t);
        off[b]++;
    }
    while (K--) {
        for (int i = 1; i <= n; i++)
            arri[i] = max(arri[i - 1], on[i - 1]) + d[i - 1];
        int now = 0;
        for (int i = n; i >= 2; i--) {
            // if (!d[i - 1]) use[i - 1] = 0;
            // else {
                use[i - 1] = off[i];
                if (arri[i] > on[i]) use[i - 1] += use[i];
            // }
        }
        int id = 0;
        for (int i = 1; i < n; i++)
            if (use[i] > use[id] && d[i] > 0) id = i;
        d[id]--;
    }
    for (int i = 1; i <= n; i++)
        arri[i] = max(arri[i - 1], on[i - 1]) + d[i - 1];
    for (int i = 1; i <= n; i++) ans += arri[i] * off[i];
    printf("%d\n", ans);
    return 0;
}

费用流

网上只有一个费用流题解 T^T 那位大神也是超级厉害！

首先由 $S$ 向 $S’$ 连一条流量为 $K$，费用为 $0$ 的边（限制总流量为 $K$）

把每个点 $i$ 拆为 $i’$ 和 $i’’$。

  1. $(i’, i’’, max(tim[i] - on[i], 0), 0)$，其中 $tim[i]$ 表示不加任何加速器时车到达 $i$ 点的时间，$on[i]$ 表示 $i$ 点最晚上车的时间。一旦加速器使用超过 $tim[i] - on[i]$ 了，多余的部分就会没用，所以就别浪费了

  2. $(i’’, (i + 1)’, \infty, -off[i])$，其中 $off[i]$ 表示 $i$ 点下车的人

  3. $(S’, i’’, D[i]（这应该也是在限制该边总流量不超过 D[i]）, 0)$

  4. $(i’, T, \infty, 0)$

code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10, M = 1e4 + 10, T = 1e5 + 10, inf = 0x3f3f3f3f;
int n, m, K, ans, s, t;
int D[N], on[T], off[T], tim[N];
struct node { int t, a, b; }p[M];
struct edge { int u, v, c, cost; };
vector<edge> edges;
vector<int> G[N << 1];
int dis[N << 1], inq[N << 1], pre[N << 1], fl[N << 1];
queue<int> q;

void add(int s, int t, int c, int v) {
    edges.push_back((edge){s, t, c, v});
    edges.push_back((edge){t, s, 0, -v});
    int tot = edges.size();
    G[s].push_back(tot - 2);
    G[t].push_back(tot - 1);
}

bool spfa(int s, int t, int &flow, int &cost) {
    memset(dis, 0x3f, sizeof(dis));
    memset(inq, 0, sizeof(inq));
    q.push(s);
    dis[s] = 0, inq[s] = 1, fl[s] = inf, pre[s] = 0;
    while (q.size()) {
        int u = q.front(); q.pop(); inq[u] = 0;
        for (int i = 0; i < G[u].size(); i++) {
            edge e = edges[G[u][i]];
            if (e.c && dis[e.v] > dis[e.u] + e.cost) {
                dis[e.v] = dis[e.u] + e.cost;
                pre[e.v] = G[u][i];
                fl[e.v] = min(fl[e.u], e.c);
                if (!inq[e.v]) {
                    inq[e.v] = 1; q.push(e.v);
                }
            }
        }
    }
    if (dis[t] == inf) return 0;
    flow += fl[t];
    cost += fl[t] * dis[t];
    int pos = t;
    while (pos != s) {
        edges[pre[pos]].c -= fl[t];
        edges[pre[pos] ^ 1].c += fl[t];
        pos = edges[pre[pos]].u;
    }
    return 1;
}

int Mincost() {
    int flow = 0, cost = 0;
    while (spfa(s, t, flow, cost));
    return cost;
}

int main() {
    scanf("%d%d%d", &n, &m, &K);
    for (int i = 1; i < n; i++) scanf("%d", &D[i]);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &p[i].t, &p[i].a, &p[i].b);
        on[p[i].a] = max(on[p[i].a], p[i].t);
        off[p[i].b]++;
    }
    for (int i = 1; i <= n; i++) tim[i] = max(tim[i - 1], on[i - 1]) + D[i - 1];
    for (int i = 1; i <= m; i++) ans += tim[p[i].b] - p[i].t;

    s = n * 2 + 1, t = n * 2 + 3;
    int s1 = n * 2 + 2;
    add(s, s1, K, 0);
    for (int i = 1; i < n; i++) {
        add(i, i + n, max(tim[i] - on[i], 0), 0);
        add(i + n, i + 1, inf, -off[i + 1]);
        add(s1, i + n, D[i], 0);
        add(i + 1, t, inf, 0);
    }
    printf("%d\n", ans + Mincost());
    return 0;
}

好鬼畜啊。。。是目前做过最奇技淫巧的网络流。。。